package algorithm.structure.tree.common;

import algorithm.structure.tree.inter.BaseNodeSYT;
import algorithm.structure.tree.inter.BaseTreeSYT;

public class TreeSYT implements BaseTreeSYT{
	private NodeSYT root;
	public BaseNodeSYT insertNode(NodeSYT node){
		if(root == null){
			root = node;
			return root;
		}
		NodeSYT p = null;
		NodeSYT nodeCopy = root;
		while(nodeCopy != null){
			p = nodeCopy;
			if(node.getNodeKey().compareTo(nodeCopy.getNodeKey()) >= 0){
				nodeCopy = nodeCopy.getRightChild();
			}else{
				nodeCopy = nodeCopy.getLeftChild();
			}
		}
		if(node.getNodeKey().compareTo(p.getNodeKey()) >= 0){
			p.setRightChild(node);
		}else{
			p.setLeftChild(node);
		}
		node.setParent(p);
		return node;
	}
	public NodeSYT deleteNode(NodeSYT node){
		if(node.getLeftChild() == null){
			transplant(node,node.getRightChild());
		}else if(node.getRightChild() == null){
			transplant(node,node.getLeftChild());
		}else{
			NodeSYT successor = getMinNum(node.getRightChild());
			if(successor.getParent() != node){
				transplant(successor,successor.getRightChild());
				successor.setRightChild(node.getRightChild());
				successor.getRightChild().setParent(successor);
			}
			transplant(node,successor);
			successor.setLeftChild(node.getLeftChild());
			successor.getLeftChild().setParent(successor);
		}
		return node;
	}
	public NodeSYT getMinNum(){
		return getMinNum(root);
	}
	public NodeSYT getMaxNum(){
		return getMaxNum(root);
	}
	public NodeSYT getMinNum(NodeSYT node){
		NodeSYT nodeCopy = node;
		if(nodeCopy == null){
			return nodeCopy;
		}
		
		while(nodeCopy.getLeftChild() != null){
			nodeCopy = nodeCopy.getLeftChild(); 
		}
		return nodeCopy;
	}
	public NodeSYT getMaxNum(NodeSYT node){
		NodeSYT nodeCopy = node;
		if(nodeCopy == null){
			return nodeCopy;
		}
		while(nodeCopy.getRightChild() != null){
			nodeCopy = nodeCopy.getRightChild(); 
		}
		return nodeCopy;
	}
	public NodeSYT getRoot() {
		return root;
	}
	public void setRoot(NodeSYT root) {
		this.root = root;
	}
	public NodeSYT getsuccessor(NodeSYT node){
		if(node.getRightChild() != null){
			return getMinNum(node.getRightChild());
		}
		NodeSYT y = node.getParent();
		while(y != null && y.getParent().getRightChild() == node){
			node = y;
			y = y.getParent();
		}
		return y;
	}
	private void transplant(NodeSYT nodeTo,NodeSYT nodeFrom){
		if(nodeTo.getParent() == null){
			root = nodeFrom;
		}else if(nodeTo.getParent().getLeftChild() == nodeTo){
			nodeTo.getParent().setLeftChild(nodeFrom);
		}else{
			nodeTo.getParent().setRightChild(nodeFrom);
		}
		if(nodeFrom != null){
			nodeFrom.setParent(nodeTo.getParent());
		}
	}
	
	public NodeSYT addNode(int value){
		NodeKeySYT nodeNodeKey = new NodeKeySYT();
		nodeNodeKey.setValue(value);
		NodeSYT node = new NodeSYT();
		node.setNodeKey(nodeNodeKey);
		insertNode(node);
		return node;
	}
	
	
	//节点左旋转
	public void leftRotate(NodeSYT x){
		NodeSYT y = x.getRightChild();
		x.setRightChild(y.getLeftChild());
		if(y.getLeftChild() != null){
			y.getLeftChild().setParent(x);
		} 
		y.setParent(x.getParent());
		if(x.getParent() == null){
			root = y;
		}else if(x == x.getParent().getLeftChild()){
			x.getParent().setLeftChild(y);
		}else{
			x.getParent().setRightChild(y);
		}
		y.setLeftChild(x);
		x.setParent(y);
		
	}
	
	//节点右旋转
	public void tRotate(NodeSYT y){
		NodeSYT x = y.getLeftChild();
		y.setLeftChild(x.getRightChild());
		if(x.getRightChild() != null){
			x.getRightChild().setParent(y);
		} 
		x.setParent(y.getParent());
		if(y.getParent() == null){
			root = x;
		}else if(y == y.getParent().getLeftChild()){
			y.getParent().setLeftChild(x);
		}else{
			y.getParent().setRightChild(x);
		}
		x.setRightChild(y);
		y.setParent(x);
	}
}
